



/* 
 * UCLA CS 111 - Fall 2010 - Lab 1
 * Skeleton code for commandline parsing for Lab 1 - Shell processing
 * This file contains the skeleton code for parsing input from the command
 * line.
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>
#include <errno.h>
#include "cmdline.h"



// code  block below allows usage of "bool" and "boolean"
#define TRUE  1
#define FALSE 0
#define true  1
#define false 0
typedef int boolean;
typedef int bool;

// extra credit on/off; debugging purpose
bool extra_credit = true;
bool debugging_info = false;


/*
 * parsestate_t
 *
 *   The parsestate_t object represents the current state of the command line
 *   parser.  'parse_init' initializes a parsestate_t object for a command
 *   line, then calls to 'parse_gettoken' step through the command line one
 *   token at a time.  'parse_ungettoken' backs up one token.
 */




/*
 * parse_init(parsestate, line)
 *
 *   Initialize a parsestate_t object for a given command line.
 */

void
parse_init(parsestate_t *parsestate, char *input_line)
{


	parsestate->position = input_line;
	parsestate->last_position = NULL;
}


bool
isTermChar(char ch)
{
  if(ch == '\0')
    return true;
  if(ch == '\n')
    return true;
  if(isspace(ch))
    return true;
  if(extra_credit)
    {

      switch(ch)
	{
	case '(':
	case ')':
	case ';':
	case '|':
	case '&':
	case '>':
	case '<':
	  return true;
	default:
	  return false;
	}
    }
  else{
    return false;
  }
}
bool
insideToken(char *str, bool open_quote, token_t *token)
{
  if (!open_quote)
    {
      return *str != '\n' && *str != '\0' && !isspace(*str);
    }
  else
    {
      if(*str == '\n' || *str == '\0')
	{
	  token->buffer[0] = '\0';
	  token->type = TOK_ERROR;
	  //exit(1);
	  return false;
	}
      return true;
    }
}

// determines token type according to token->buffer
tokentype_t
detTokenType(token_t *token)
{ 
  if(token->buffer[0] == '\0' || token->buffer[0] == '\n') {
    //printf("%c This is a TOK_END.\n", token->buffer[0]);
    return TOK_END;
  }
  if(token->buffer[1] == '\0' || token->buffer[1] == '\n') {
    switch(token->buffer[0]) {
   
    case '<':
      //printf(" This is a TOK_LESS_THAN.\n");
      return TOK_LESS_THAN;       // '<'
    case '>':
      //printf(" This is a TOK_GREATER_THAN.\n");
      return TOK_GREATER_THAN;    // '>'
    case ';':
      //printf(" This is a TOK_SEMICOLON.\n");
      return TOK_SEMICOLON;       // ';'
    case '&':
      //printf(" This is a TOK_AMPERSAND.\n");
      return TOK_AMPERSAND;       // '&'
    case '|':
      // printf(" This is a TOK_PIPE.\n");
      return TOK_PIPE;            // '|'
    case '(':
      // printf(" This is a TOK_OPEN_PAREN.\n");
      return TOK_OPEN_PAREN;      // '('
    case ')':
      // printf(" This is a TOK_CLOSE_PAREN.\n");
      return TOK_CLOSE_PAREN;      // ')'
    default:
      //printf(" This is a TOK_NORMAL.\n");
      return TOK_NORMAL;
    }
  }
    else {
      if(token->buffer[2] == '\0') {
	if(token->buffer[0] == '2' && token->buffer[1] == '>') {
	  //printf(" This is a TOK_2_GREATER_THAN.\n");
	  return TOK_2_GREATER_THAN;
	}

	if(token->buffer[0] == '&' && token->buffer[1] == '&') {
	  //printf(" This is a TOK_DOUBLEAMP.\n");
	  return TOK_DOUBLEAMP;
	}

	if(token->buffer[0] == '|' && token->buffer[1] == '|'){
	  //printf(" This is a TOK_DOUBLEPIPE.\n");
	  return TOK_DOUBLEPIPE;
	}
      }
  }

  //printf(" This is a TOK_NORMAL.\n");
  return TOK_NORMAL;
}


/*my own function to skip all whitespace from a char*
returns the new char* that starts with a non-whitspace */
char*
skip_wspace(char *str)
{
  while(*str != '\n' && isspace(*str))
	  {
	    // while the current char is a space go to the next char.
	    str = str + 1;
	   
	  }
  return str;
}

/*
 * parse_ettoken(parsestate, token)
 *
 *   Fetches the next token from the input line.
 *   The token's type is stored in 'token->type', and the token itself is
 *   stored in 'token->buffer'.  The parsestate itself is moved past the
 *   current token, so that the next call to 'parse_gettoken' will return the
 *   next token.
 *   Tokens are delimited by space characters. Any leading space is skipped.
 *
 *   EXERCISES:
 *        1. The example function just reads the whole command line into a
 *           single token (it ignores spaces). Make it stop when it reaches the
 *           end of a token, as delimited by "whitespace" (a C term for
 *           blank characters, including tab '\t' and newline '\n'.  Hint:
 *           man isspace)
 *        2. Add support for "double quotes".  If the parsestate contains
 *           the string ==> "a b" c <== (arrows not included), then the next
 *           call to 'parse_gettoken' should stick the string "a b" into
 *           'token', and move the parsestate to "c" or " c".
 *   EXTRA CREDIT EXERCISE:
 *        3. Allow special characters like ';' and '&' to terminate a token.
 *           In real shells, "a;b" is treated the same as "a ; b".
 *           The following characters and two-character sequences should
 *           end the current token, except if they occur in double quotes.
 *           Of course, you can return one of these sequences as a token
 *           when it appears first in the string.
 *                (  )  ;  |  &  &&  ||  >  <
 *           Note that "2>" does not end a token.  The string "x2>y" is parsed
 *           as "x2 > y", not "x 2> y".
 */

void
parse_gettoken(parsestate_t *parsestate, token_t *token)
{
  
	int i;
	char *str = parsestate->position;	// current string
	int quote_state;			// Hint!
	int any_quotes;				// Hint!

	//initialize the token type
	token->type = '\0';

	// EXERCISE: Skip initial whitespace in 'str'.
	
	/* Your code here. */
	/* Done */
	str = skip_wspace(str);
	
	// Report TOK_END at the end of the command string.
	if (*str == '\0') {
		// Save initial position so parse_ungettoken() will work
		parsestate->last_position = parsestate->position;
		token->buffer[0] = '\0';	// empty token
		token->type = TOK_END;
		
		return;
	}


	// EXERCISE: Store the next token into 'token', and terminate the token
	// with a null character.  Handle quotes properly.  Store at most
	// TOKENSIZE - 1 characters into 'token' (plus a terminating null
	// character); longer tokens should cause an error.

	// The current code treats the entire rest of the string as a token.
	// Change this code to handle quotes and terminate tokens at spaces.

	i = 0;

	// variable below indicates whether we are in a quoted token
	int open_quote = 0;
	char prev_char = '\0';
	// while we are within a token
	
 	while (insideToken(str, open_quote, token)) {
	
	  if (i >= TOKENSIZE - 1)
	    // Token too long; this is an error
	    goto error;

	  if (*str == '\"' || *str == '\'') {
	    if (!open_quote)
	    {
	      if(*str == '\"') {

		open_quote = 2;
	      }
	      else if (*str == '\'') {
		open_quote = 1;
	      }
	      
	      token->type = TOK_NORMAL;
	      str++;
	    }
	    else {
	      if(open_quote == 1)
		{
		  if(*str == '\'')
		    {

		      open_quote = 0;
		      str++;
		    }
		  else
		    {
		       token->buffer[i++] = *str++;
		    }
		}
	      else if(open_quote == 2)
	     	{
		  if(*str == '\"')
		    {

		      open_quote = 0;
		      str++;
		    }
		  else
		    {
		       token->buffer[i++] = *str++;
		    }
		}
	      
	    }
	  }
	  else {
	   
	    token->buffer[i++] = *str++;
	  }

	}
	
	

	token->buffer[i] = '\0';	// end the token string
       
	//printf("%s\n", token->buffer);

	// Save initial position so parse_ungettoken() will work
	parsestate->last_position = parsestate->position;
	// Move current position in place for the next token
	parsestate->position = str;


	// EXERCISE: Examine the token and store its type in token->type.
	// Quoted special tokens, such as '">"', have type TOK_NORMAL.

	/* Your code here. */
	
	if (!(token->type))
	    token->type = detTokenType(token);
       
	//printf("buffer: %s\n", token->buffer);
	return;

 error:
	token->buffer[0] = '\0';
	token->type = TOK_ERROR;
}

/*
 * parse_ungettoken(parsestate)
 *
 *   Backs up the parsestate by one token.
 *   It's impossible to back up more than one token; if you call
 *   parse_ungettoken() twice in a row, the second call will fail.
 */

void
parse_ungettoken(parsestate_t *parsestate)
{
	// Can't back up more than one token.
	assert(parsestate->last_position != NULL);
	parsestate->position = parsestate->last_position;
	parsestate->last_position = NULL;
}


/*
 * command_alloc()
 *
 *   Allocates and returns a new blank command.
 */

command_t *
command_alloc(void)
{
	// Allocate memory for the command
	command_t *cmd = (command_t *) malloc(sizeof(*cmd));
	if (!cmd)
		return NULL;
	
	// Set all its fields to 0
	memset(cmd, 0, sizeof(*cmd));

	return cmd;
}


/*
 * command_free()
 *
 *   Frees all memory associated with a command.
 *
 *   EXERCISE:
 *        Fill in this function.
 *        Also free other structures pointed to by 'cmd', including
 *        'cmd->subshell' and 'cmd->next'.
 *        If you're not sure what to free, look at the other code in this file
 *        to see when memory for command_t data structures is allocated.
 */

void
command_free(command_t *cmd)
{
	int i;
	
	// It's OK to command_free(NULL).
	if (!cmd)
		return;

	command_free(cmd->subshell);
	command_free(cmd->next);
	free(cmd);
	/* Your code here. */
}


/*
 * command_parse(parsestate)
 *
 *   Parses a single command_t structure from the input string.
 *   Returns a pointer to the allocated command, or NULL on error
 *   or if the command is empty. (One example is if the end of the
 *   line is reached, but there are other examples too.)
 *
 *   EXERCISES:
 *        The current version of the function just grabs all the tokens
 *        from 'input' and doesn't stop on command-delimiting tokens.
 *        Your job is to enhance its error checking (to avoid exceeding
 *        the maximum number of tokens in a command, for example), to make it
 *        stop at the end of the command, and to handle parentheses and
 *        redirection correctly.
 */

command_t *
command_parse(parsestate_t *parsestate)
{
	int i = 0;
	command_t *cmd = command_alloc();
	if (!cmd)
		return NULL;
	
	int got_out_of_sub = 0;
	
	while (1) {


	        /** NOTE: THIS ERROR CHECK IS DONE IN THE WHILE LOOP ****/



		// Third, a parenthesized subcommand can't be part of the
		// same command as other normal tokens.  For example,
		// "echo ( echo foo )" and "( echo foo ) echo" are both errors.
		// (You should figure out exactly how to check for this kind
		// of error. Try interacting with the actual 'bash' shell
		// for some ideas.)
		// 'goto error' when you encounter one of these errors,
		// which frees the current command and returns NULL.

		// Hint: An open parenthesis should recursively call
		// command_line_parse(). The command_t structure has a slot
		// you can use for parens; figure out how to use it!

	       /******* END OF ERROR CHECKING ********/


	  // Get the next token
		token_t token;
		parse_gettoken(parsestate, &token);



		// Normal tokens go in the cmd->argv[] array.
		// Redirection file names go into cmd->redirect_filename[].
		// Open parenthesis tokens indicate a subshell command.
		// Other tokens complete the current command
		// and are not actually part of it;
		// use parse_ungettoken() to save those tokens for later.





	        
		switch (token.type) {

		  // In normal case we store the token to the command buffer
		case TOK_NORMAL:
		  
		  // First, be careful about overflow on normal tokens.
		  // Each command_t only has space for MAXTOKENS tokens in
		  // 'argv'. If there are too many tokens, reject the whole
		  // command.


		        // Make sure that token.buffer size is less than or equal MAX_TOKEN
		        if(strlen(token.buffer) > MAXTOKENS) goto error;

			cmd->argv[i] = strdup(token.buffer);
			i++;
			break;
		
		// In open parenthesis, we want to call command_line_parse, to build a whole command. 
		// and connect the next command to this command with the subshell field
		case TOK_OPEN_PAREN:
		  
		  // Assuming that if this isnt the first thing / command then its an error
		  if ( i != 0 ) goto error;
		  
		  // give parsestate and say we are in a parenthesis.
		  command_t* subshell_command = command_line_parse(parsestate, 1);
		   
		  if(subshell_command == NULL) goto error;
		  
		  cmd->subshell = subshell_command; 
		 
		  
		  i++; // So we can return the cmd in done
		  
		  goto done;
		  break;



		// 
			
		/*** 
		     Figure out the I/O redirection stuff, meaning we will save
		     get the next normal token, and save it to the right place in redir_filename.
		***/

		// Second, redirection tokens (<, >, 2>) must be followed by
		// TOK_NORMAL tokens containing file names.
		
		case  TOK_LESS_THAN:       // '<' or STDIN
		  // Get the next token
		  parse_gettoken(parsestate, &token);
		  
		  // If the next token isn't a normal token, then there's an error
		  if(token.type != TOK_NORMAL) goto error;
		  
		  // Assuming token is normal.
		  // Store the normal token in STDIN slot of redir_filename (0)
		  cmd->redirect_filename[0] = strdup(token.buffer);
		  break;


		case TOK_GREATER_THAN:    // '>' or STDOUT
		  // Get the next token
		  parse_gettoken(parsestate, &token);
		  
		  // If the next token isn't a normal token, then there's an error
		  if(token.type != TOK_NORMAL) goto error;
		  
		  // Assuming token is normal.
		  // Store the normal token in STDOUT slot of redir_filename (1)
		  cmd->redirect_filename[1] = strdup(token.buffer);
		  break;


		case TOK_2_GREATER_THAN:  // '2>' or STDERR
		  // Get the next token
		  parse_gettoken(parsestate, &token);
		  
		  // If the next token isn't a normal token, then there's an error
		  if(token.type != TOK_NORMAL) goto error;
		  
		  // Assuming token is normal.
		  // Store the normal token in STDERR slot of redir_filename (2)
		  cmd->redirect_filename[2] = strdup(token.buffer);
		  break;
		
		  
		  // When we get to a special token, then we stop and return because we are only parsing one single command
	
		case TOK_END:
		  cmd->controlop = TOK_END;
		  goto done;
		  break;

		default:
			parse_ungettoken(parsestate);
			goto done;
		}
	}

 done:
	// NULL-terminate the argv list
	cmd->argv[i] = 0;

	// EXERCISE: Make sure you return the right return value!

	if (i == 0) {
		/* Empty command */
		command_free(cmd);
		return NULL;
	} else
		return cmd;
	
 error:
	command_free(cmd);
	return NULL;
}


/*
 * command_line_parse(parsestate, in_parens)
 *
 *   Parses a command line from 'input' into a linked list of command_t
 *   structures. The head of the linked list is returned, or NULL is
 *   returned on error.
 *   If 'in_parens != 0', then command_line_parse() is being called recursively
 *   from command_parse().  A right parenthesis should end the "command line".
 *   But at the top-level command line, when 'in_parens == 0', a right
 *   parenthesis is an error.
 * 
 *   Basically tries to parse on shell command (or subshell command)
 */



command_t *
command_line_parse(parsestate_t *parsestate, int in_parens)
{
	command_t *prev_cmd = NULL;
	command_t *head = NULL;
	command_t *cmd;
	token_t token;
	int r;

	int canEnd = 0;

	// This loop has to deal with command syntax in a smart way.
	// Here's a nonexhaustive list of the behavior it should implement
	// when 'in_parens == 0'.

	// COMMAND                             => OK
	// COMMAND ;                           => OK
	// COMMAND && COMMAND                  => OK
	// COMMAND &&                          => error (can't end with &&)
	// COMMAND )                           => error (but OK if "in_parens")
	
	while (1) {
		// Parse the next command.
		cmd = command_parse(parsestate);
	
		// ME: This is the "glue", how to link up the current command with the next command (if any).
		
		// Get the next token
		parse_gettoken(parsestate, &token);
		
		if (!cmd && canEnd > 0 )	
		  goto done;
		else if (!cmd) goto error;

		// Link the command up to the command line.
		if (prev_cmd)
			prev_cmd->next = cmd;
		else
			head = cmd;
		prev_cmd = cmd;

		// EXERCISE: Fetch the next token to see how to connect this
		// command with the next command. React to errors with
		// 'goto error'. The ";" and "&" tokens may require special
		// handling, since unlike other special tokens, they can end
		// the command line.
		
		
	
		

		// If the next token is a special token that needs another command, keep going
		// otherwise we're done.
	
		switch (token.type){
		  
		   case TOK_AMPERSAND:
		   case TOK_SEMICOLON:
		     canEnd = 1;
		     cmd->controlop = token.type;
		     break;
		    
		

		  // Link up the control op with the current command
		  // cmd->controlop = token.type;
		  // goto done;
		
		  
		  //break;
	       
		case TOK_CLOSE_PAREN:
		  if(in_parens > 0) {
		    
		    // Link up the control op with the current command
		    cmd->controlop = CMD_END;

		    goto done;
		
		  }else goto error;
		  
		case TOK_END:
		  // Means the end of the string, 

		  // if we were in parens, then this is an error because there was no closing parens
		  if (in_parens > 0 ) goto error;
		  else goto done;
		  break;
		  



		  			
		/*** 
		     Figure out the I/O redirection stuff, meaning we will save
		     get the next normal token, and save it to the right place in redir_filename.
		***/

		// Second, redirection tokens (<, >, 2>) must be followed by
		// TOK_NORMAL tokens containing file names.
		
		case  TOK_LESS_THAN:       // '<' or STDIN
		  // Get the next token
		  parse_gettoken(parsestate, &token);
		  
		  // If the next token isn't a normal token, then there's an error
		  if(token.type != TOK_NORMAL) goto error;
		  
		  // Assuming token is normal.
		  // Store the normal token in STDIN slot of redir_filename (0)
		  cmd->redirect_filename[0] = strdup(token.buffer);
		  break;


		case TOK_GREATER_THAN:    // '>' or STDOUT
		  // Get the next token
		  parse_gettoken(parsestate, &token);
		  
		  // If the next token isn't a normal token, then there's an error
		  if(token.type != TOK_NORMAL) goto error;
		  
		  // Assuming token is normal.
		  // Store the normal token in STDOUT slot of redir_filename (1)
		  cmd->redirect_filename[1] = strdup(token.buffer);


		  // Check if the next token is an end, if so we are done.
		  parse_gettoken(parsestate, &token);
		  
		  if(token.type == TOK_END){
		    cmd->controlop = TOK_END;
		    goto done;
		  }else parse_ungettoken(parsestate);
		  
		  break;


		case TOK_2_GREATER_THAN:  // '2>' or STDERR
		  // Get the next token
		  parse_gettoken(parsestate, &token);
		  
		  // If the next token isn't a normal token, then there's an error
		  if(token.type != TOK_NORMAL) goto error;
		  
		  // Assuming token is normal.
		  // Store the normal token in STDERR slot of redir_filename (2)
		  cmd->redirect_filename[2] = strdup(token.buffer);
		  break;


		default:
		  
		  // Link up the control op with the current command
		  cmd->controlop = token.type;

		  
		  continue;
		  break;
		}




	}

 done:
	// EXERCISE: Check that the command line ends properly.

	/* Your code here */
	
	return head;

 error:
	command_free(head);
	return NULL;
}


/*
 * commandlist_print(command, indent)
 *
 *   Prints a representation of the command to standard output.
 */

void
command_print(command_t *cmd, int indent)
{
	int argc, i;
	
	if (cmd == NULL) {
		printf("%*s[NULL]\n", indent, "");
		return;
	}

	for (argc = 0; argc < MAXTOKENS && cmd->argv[argc]; argc++)
		/* do nothing */;

	// More than MAXTOKENS is an error
	assert(argc <= MAXTOKENS);

	printf("%*s[%d args", indent, "", argc);
	for (i = 0; i < argc; i++)
		printf(" \"%s\"", cmd->argv[i]);

	// Print redirections
	if (cmd->redirect_filename[STDIN_FILENO])
		printf(" <%s", cmd->redirect_filename[STDIN_FILENO]);
	if (cmd->redirect_filename[STDOUT_FILENO])
		printf(" >%s", cmd->redirect_filename[STDOUT_FILENO]);
	if (cmd->redirect_filename[STDERR_FILENO])
		printf(" 2>%s", cmd->redirect_filename[STDERR_FILENO]);

	// Print the subshell command, if any
	if (cmd->subshell) {
		printf("\n");
		command_print(cmd->subshell, indent + 2);
	}
	
	printf("] ");
	switch (cmd->controlop) {
	case TOK_SEMICOLON:
		printf(";");
		break;
	case TOK_AMPERSAND:
		printf("&");
		break;
	case TOK_PIPE:
		printf("|");
		break;
	case TOK_DOUBLEAMP:
		printf("&&");
		break;
	case TOK_DOUBLEPIPE:
		printf("||");
		break;
	case TOK_END:
		// we write "END" as a dot
		printf(".");
		break;
	default:
		assert(0);
	}

	// Done!
	printf("\n");

	// if next is NULL, then controlop should be CMD_END, CMD_BACKGROUND,
	// or CMD_SEMICOLON
	assert(cmd->next || cmd->controlop == CMD_END
	       || cmd->controlop == CMD_BACKGROUND
	       || cmd->controlop == CMD_SEMICOLON);

	if (cmd->next)
		command_print(cmd->next, indent);
}
